// 定义链表节点的构造函数
function ListNode(val, next) {
    this.val = (val === undefined ? 0 : val);
    this.next = (next === undefined ? null : next);
}


// l1 和 l2 为当前遍历的节点，carry 为进位
// 这里编写函数：
//=======================================
var addTwoNumbers = function(l1, l2, carry = 0) {
    if (l1 === null && l2 === null && carry === 0) { // 递归边界
        return null;
    }

    let s = carry;
    if (l1) {
        s += l1.val; // 累加进位与节点值
        l1 = l1.next;
    }
    if (l2) {
        s += l2.val;
        l2 = l2.next;
    }

    // s 除以 10 的余数为当前节点值，商为进位
    return new ListNode(s % 10, addTwoNumbers(l1, l2, Math.floor(s / 10)));
};

// 辅助函数：根据数字创建链表（例如，100 -> ListNode(1, ListNode(0, ListNode(0, null)))）
function createLinkedList(num) {
    // 处理特殊情况 num = 0
    if (num === 0) {
        return new ListNode(0);
    }
    
    let head = null;
    let current = null;
    
    // 从数字的个位开始，依次创建节点
    while (num > 0) {
        const digit = num % 10;
        const newNode = new ListNode(digit);
        
        if (head === null) {
            head = newNode;
            current = newNode;
        } else {
            current.next = newNode;
            current = current.next;
        }
        
        num = Math.floor(num / 10);
    }
    
    return head;
}

// 辅助函数：将链表转换为数字（用于验证结果）
function linkedListToNumber(head) {
    let num = 0;
    let multiplier = 1; // 代表个位、十位、百位...
    let current = head;
    
    while (current !== null) {
        num += current.val * multiplier;
        multiplier *= 10;
        current = current.next;
    }
    
    return num;
}

// --- 现在开始测试 ---

// 1. 定义要相加的两个数
const num1 = 100;
const num2 = 200;

// 2. 根据数字创建对应的链表
const l1 = createLinkedList(num1);
const l2 = createLinkedList(num2);

// 3. 调用 addTwoNumbers 函数
const resultList = addTwoNumbers(l1, l2);

// 4. 将结果链表转换为数字，以便查看
const resultNum = linkedListToNumber(resultList);

// 5. 打印结果
console.log(`${num1} + ${num2} = ${resultNum}`); // 输出：100 + 200 = 300

// 再测试一个更复杂的例子，比如 999 + 2
const num3 = 999;
const num4 = 2;
const l3 = createLinkedList(num3);
const l4 = createLinkedList(num4);
const resultList2 = addTwoNumbers(l3, l4);
const resultNum2 = linkedListToNumber(resultList2);
console.log(`${num3} + ${num4} = ${resultNum2}`); // 输出：999 + 2 = 1001